package 力扣._29两数相除;

class Solution {
    int divide(int dividend, int divisor) {
        // 特殊边界
        // 被除数为最小值 -2^31
        if(dividend == Integer.MIN_VALUE){
            if(divisor==1)
                return dividend;
            else if(divisor==-1) // 此时 商 2^31 > 2^31-1 溢出
                return Integer.MAX_VALUE;
        }
        // 考虑除数为最小值的情况
        if(divisor == Integer.MIN_VALUE){
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        if(dividend == 0)
            return 0;

        // 二分
        boolean isN = (dividend < 0 ^ divisor <0); //异或，同0异1
        // 让全为负数
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);

        int left = 1, right = Integer.MAX_VALUE, mid,ans = 0;
        while(left<=right){
            mid = left + ((right - left) >> 1);
            boolean check = quickAdd(divisor,mid,dividend);
            if(check){
                ans = mid;
                if(mid == Integer.MAX_VALUE)
                    break;
                left = mid + 1;
            }else
                right = mid - 1;

        }
        return isN ? -ans : ans;
        
    }

    // 判断 z*y >= x 是否成立
    boolean quickAdd(int y, int z, int x){
        int r = 0, add = y;
        while(z!=0){
            if((z & 1) != 0){     // 当前位不为0
                if(r < x - add)
                    return false;
                r += add;
            }
            if(z != 1){
                if( add < x - add)
                    return false;
                add += add;
            }

            z >>= 1;
        }
        return true;
    }    // 判断 z*y >= x 是否成立
    boolean quickAdd2(int a, int b, int x){
        int result = 0;
        while (b != 0) {
            if ((b & 1) == 1) { // If the current bit is 1
                result += a;
            }
            a <<= 1; // a left shift by one bit, equivalent to a * 2
            b >>= 1; // b right shift by one bit, equivalent to b / 2
        }
        return result >= x;
    }


    public static void main(String[] args) {
        System.out.println(3<0 ^ 10<0);
        System.out.println(3<0 ^ -1<0);
        int d = new Solution().divide(10, 3);
        System.out.println(d);
    }
}